#include <string>
#include <vector>

using namespace std;


/**
 * @brief 567. 字符串的排列
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
 * 如果是，返回 true ；否则，返回 false 。
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 * https://leetcode.cn/problems/permutation-in-string/
 */
class Solution {
public:
    //* 如果出现了 cnt[x] > 0 的情况，那么：
    //*     1. x 不存在于 s1 中，因此需要一直移动 l 指针到 x 右侧
    //*     2. x 数量超过 s1 中 x 数量，因此需要移动 l 指针到最先
    //*        出现的 x 右侧
    bool checkInclusion(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) return false;

        vector<int> cnt(26);
        for (int i=0; i<m; i++) cnt[s1[i]-'a']--;

        int l = 0;
        for (int r=0; r<n; r++) {
            int x = s2[r] - 'a';
            cnt[x]++;
            while (cnt[x]>0) cnt[s2[l++]-'a']--;  // 多余了 移动左边
            if (r-l+1 == m) return true;
        }

        return false;
    }
};
